{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Zigzag Level Order Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: zigzagLevelOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的锯齿形层序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> ，返回其节点值的 <strong>锯齿形层序遍历</strong> 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg\" style=\"width: 277px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>[[3],[20,9],[15,7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[[1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[0, 2000]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-zigzag-level-order-traversal](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-zigzag-level-order-traversal](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[1]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import queue\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        q = queue.Queue()\n",
    "        q.put((root, 0))\n",
    "        res = []        \n",
    "        while not q.empty():\n",
    "            node, level = q.get()\n",
    "            if node:\n",
    "                if len(res) <= level:\n",
    "                    res.append([])\n",
    "                res[level].append(node.val)\n",
    "                q.put((node.left, level + 1))\n",
    "                q.put((node.right, level + 1))\n",
    "        \n",
    "        for i in range(len(res)):\n",
    "            if i % 2 == 1:\n",
    "                res[i].reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        ret, queue = [], []\n",
    "        cur_depth, cur_level = -1, None\n",
    "        if root:\n",
    "            queue.append((root, 0))\n",
    "        while queue:\n",
    "            node, depth = queue.pop(0)\n",
    "            if depth != cur_depth:\n",
    "                if cur_level:\n",
    "                    if cur_depth % 2:\n",
    "                        ret.append(cur_level[::-1])\n",
    "                    else:\n",
    "                        ret.append(cur_level)\n",
    "                cur_level = []\n",
    "                cur_depth = depth\n",
    "            cur_level.append(node.val)\n",
    "            if node.left:\n",
    "                queue.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, depth + 1))\n",
    "        if cur_level:\n",
    "            if cur_depth % 2:\n",
    "                ret.append(cur_level[::-1])\n",
    "            else:\n",
    "                ret.append(cur_level)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        return self.way1(root)\n",
    "    def way1(self,root):\n",
    "        def level_Order(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            ans = []\n",
    "            cur_level = []\n",
    "            cur_level.append(root)\n",
    "            while cur_level:\n",
    "                next_level = []\n",
    "                ans.append([node.val for node in cur_level])\n",
    "                for i in cur_level:\n",
    "                    if i.left:\n",
    "                        next_level.append(i.left)\n",
    "                    if i.right:\n",
    "                        next_level.append(i.right)\n",
    "                cur_level = next_level\n",
    "            return ans\n",
    "        ans = level_Order(root)\n",
    "        for i in range(len(ans)):\n",
    "            if i % 2 != 0:\n",
    "                ans[i] = ans[i][::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        levelnodes = [root]\n",
    "        i = 1\n",
    "        while levelnodes:\n",
    "            res.append([node.val for node in levelnodes])\n",
    "            nextlevel = []\n",
    "            levelnodes.reverse()\n",
    "            for node in levelnodes:\n",
    "                if i%2==0:\n",
    "                    if node.left:\n",
    "                        nextlevel.append(node.left)\n",
    "                    if node.right:\n",
    "                        nextlevel.append(node.right)\n",
    "                else:\n",
    "                    if node.right:\n",
    "                        nextlevel.append(node.right)\n",
    "                    if node.left:\n",
    "                        nextlevel.append(node.left)\n",
    "            i += 1\n",
    "            levelnodes = nextlevel\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def levelRecord(level, result, order):\n",
    "            nextLevel = []\n",
    "\n",
    "            if order:\n",
    "                for node in reversed(level):\n",
    "                    result.append(node.val)\n",
    "                    if node.left:\n",
    "                        nextLevel.append(node.left)\n",
    "                    if node.right:\n",
    "                        nextLevel.append(node.right)\n",
    "            else:\n",
    "                for node in reversed(level):\n",
    "                    result.append(node.val)\n",
    "                    if node.right:\n",
    "                        nextLevel.append(node.right)\n",
    "                    if node.left:\n",
    "                        nextLevel.append(node.left)\n",
    "\n",
    "            return nextLevel\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        q = [root]\n",
    "        r = []\n",
    "        order = True\n",
    "        while q:\n",
    "            temp = []\n",
    "            q = levelRecord(q, temp, order)\n",
    "            r.append(temp)\n",
    "            order = not order\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root==None: return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        tag = 1\n",
    "        while queue:\n",
    "            templist = []\n",
    "            for i in range(len(queue)):\n",
    "                temp = queue.pop(0)\n",
    "                templist.append(temp.val)\n",
    "                if temp.left:\n",
    "                    queue.append(temp.left)\n",
    "                if temp.right:\n",
    "                    queue.append(temp.right)\n",
    "            if tag==-1:\n",
    "                templist = templist[::-1]\n",
    "            res.append(templist)\n",
    "            tag *=-1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        v_level, n_level, level, p, tag = [root], [], [], None, True\n",
    "        while v_level:\n",
    "            p = v_level.pop(0)\n",
    "            level.append(p.val)\n",
    "            if tag:\n",
    "                if p.left:\n",
    "                    n_level.insert(0, p.left)\n",
    "                if p.right:\n",
    "                    n_level.insert(0, p.right)\n",
    "            else:\n",
    "                if p.right:\n",
    "                    n_level.insert(0, p.right)\n",
    "                if p.left:\n",
    "                    n_level.insert(0, p.left)\n",
    "            if len(v_level) == 0:\n",
    "                res.append(level)\n",
    "                level, v_level= [], copy.deepcopy(n_level)\n",
    "                n_level = []\n",
    "                tag = False if tag else True\n",
    "        return res\n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        import copy\n",
    "        res = []\n",
    "        if root == None:\n",
    "            return res\n",
    "        qlist = [root]\n",
    "        flag = True\n",
    "        while qlist:\n",
    "            tlist = []\n",
    "            copy_qlist = copy.deepcopy(qlist)\n",
    "            qlist = []\n",
    "            for i in range(len(copy_qlist)):\n",
    "                tlist.append(copy_qlist[i].val)\n",
    "            for i in range(len(copy_qlist)-1, -1, -1):\n",
    "                node = copy_qlist[i]\n",
    "                if flag == True:\n",
    "                    if node.right != None:\n",
    "                        qlist.append(node.right)\n",
    "                    if node.left != None:\n",
    "                        qlist.append(node.left)\n",
    "                else:\n",
    "                    if node.left != None:\n",
    "                        qlist.append(node.left)\n",
    "                    if node.right != None:\n",
    "                        qlist.append(node.right)\n",
    "            flag = not flag\n",
    "            res.append(tlist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        import copy\n",
    "        res = []\n",
    "        if root == None:\n",
    "            return res\n",
    "        qlist = [root]\n",
    "        flag = True\n",
    "        while qlist:\n",
    "            tlist = []\n",
    "            copy_qlist = copy.deepcopy(qlist)\n",
    "            qlist = []\n",
    "            for i in range(len(copy_qlist)):\n",
    "                tlist.append(copy_qlist[i].val)\n",
    "            \n",
    "            print(tlist)\n",
    "            for i in range(len(copy_qlist)-1, -1, -1):\n",
    "                node = copy_qlist[i]\n",
    "                if flag == True:\n",
    "                    if node.right != None:\n",
    "                        qlist.append(node.right)\n",
    "                    if node.left != None:\n",
    "                        qlist.append(node.left)\n",
    "                else:\n",
    "                    if node.left != None:\n",
    "                        qlist.append(node.left)\n",
    "                    if node.right != None:\n",
    "                        qlist.append(node.right)\n",
    "            flag = not flag\n",
    "            res.append(tlist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        return self.bfs(root)\n",
    "\n",
    "    def bfs(self, root):\n",
    "\n",
    "        solutions = []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        # 记录层数信息\n",
    "        layer = 0\n",
    "        while queue:\n",
    "            # 当前为第layer层\n",
    "            layer += 1\n",
    "            # 当前层的长度\n",
    "            size = len(queue)\n",
    "            # 初始化用于存放当前层节点的列表\n",
    "            solution = []\n",
    "            for i in range(size):\n",
    "                node = queue.popleft()\n",
    "                solution.append(node.val)\n",
    "                # 下一层\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            # 奇数层\n",
    "            if layer%2:\n",
    "                solutions.append(solution)\n",
    "            # 偶数层\n",
    "            else:\n",
    "                solutions.append(solution[::-1])\n",
    "\n",
    "        return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        stk = [root]\n",
    "        n = 0  # 对数的层进行计数，奇数由右往左，偶数相反\n",
    "        while stk:\n",
    "            layer, tmp = [], []\n",
    "            for i in stk:\n",
    "                layer.append(i.val)  # 先将本层的值从左到右放上来\n",
    "                if i.left != None:\n",
    "                    tmp.append(i.left)  # 先放左树\n",
    "                if i.right != None:\n",
    "                    tmp.append(i.right)\n",
    "            stk = tmp\n",
    "            if n % 2 == 1:\n",
    "                layer = layer[::-1]\n",
    "            res.append(layer)\n",
    "            n += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        levels = []\n",
    "        if not root:\n",
    "            return levels\n",
    "        def helper(node,level):\n",
    "            if not node:\n",
    "                return\n",
    "            if len(levels) == level:\n",
    "                levels.append([])\n",
    "            levels[level].append(node.val)\n",
    "            helper(node.left,level+1)\n",
    "            helper(node.right,level+1)\n",
    "        helper(root,0)\n",
    "        # \n",
    "        for i in range(len(levels)):\n",
    "            if i % 2 == 1:\n",
    "                levels[i] = levels[i][::-1]\n",
    "        return levels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res,cur_level,count = [],[root],0\n",
    "        while cur_level:\n",
    "            temp = []\n",
    "            next_level = []\n",
    "            for i in cur_level:\n",
    "                temp.append(i.val)\n",
    "\n",
    "                if i.left:\n",
    "                    next_level.append(i.left)\n",
    "                if i.right:\n",
    "                    next_level.append(i.right)\n",
    "            if count % 2 == 0:\n",
    "                res.append(temp)\n",
    "            else:\n",
    "                res.append(temp[::-1])\n",
    "            cur_level = next_level\n",
    "            count += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        cur_level = [root]\n",
    "        res = []\n",
    "        flag = -1 #odd: return ; even : out\n",
    "        while cur_level:\n",
    "            flag = -flag\n",
    "            tmp_out=[]\n",
    "            next_level = []\n",
    "            for node in cur_level:\n",
    "                tmp_out.append(node.val)\n",
    "                if node.left:\n",
    "                    next_level.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level.append(node.right)\n",
    "                #now next_level has both nodes on the next level from left to right\n",
    "                #output cur_level in order and update cur_level\n",
    "            res.append(tmp_out[::flag])\n",
    "            cur_level=next_level\n",
    "        return res\n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        stack = [(root, 0)]\n",
    "        while stack:\n",
    "            curr, level = stack.pop()\n",
    "            if curr:\n",
    "                if level + 1 > len(res):\n",
    "                    res.append([])\n",
    "                # res[level].append(curr.val)\n",
    "                if level % 2 == 1:\n",
    "                    res[level].append(curr.val)\n",
    "                elif level % 2 == 0:\n",
    "                    res[level].insert(0, curr.val)\n",
    "                stack.append((curr.left, level + 1))\n",
    "                stack.append((curr.right, level + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        level = [root]\n",
    "        reverse = False\n",
    "        results = []\n",
    "        \n",
    "        while level:\n",
    "            next_level = []\n",
    "            next_level_val = []\n",
    "            for node in level:\n",
    "                next_level_val.append(node.val)\n",
    "                if node.left:\n",
    "                    next_level.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level.append(node.right)\n",
    "            if reverse:\n",
    "                results.append(next_level_val[::-1])\n",
    "            else:\n",
    "                results.append(next_level_val)\n",
    "            level = next_level\n",
    "            reverse = not reverse\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,queue = [],collections.deque()\n",
    "        queue.append(root)\n",
    "        level = 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                tmp.append(cur.val)\n",
    "               \n",
    "                if cur.left:queue.append(cur.left)\n",
    "                if cur.right:queue.append(cur.right)\n",
    "            level += 1\n",
    "            if level%2==0:\n",
    "                tmp.reverse()\n",
    "            \n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, temp, stack, flag=[], [], [root], 1\n",
    "        while stack:\n",
    "            for i in range(len(stack)):\n",
    "                node=stack.pop(0)\n",
    "                temp+=[node.val]\n",
    "                if node.left: stack+=[node.left]\n",
    "                if node.right: stack+=[node.right]\n",
    "            res+=[temp[::flag]]\n",
    "            temp=[]\n",
    "            flag*=-1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        curLayer=[root]\n",
    "        nextLayer=[]\n",
    "        ans=[]\n",
    "        flag=True\n",
    "        while len(curLayer)>0:\n",
    "            for node in curLayer:\n",
    "                if node.left:\n",
    "                    nextLayer.append(node.left)\n",
    "                if node.right:\n",
    "                    nextLayer.append(node.right)\n",
    "            if flag:\n",
    "                ans.append([n.val for n in curLayer])\n",
    "                flag=not flag\n",
    "            else:\n",
    "                ans.append([n.val for n in curLayer[::-1]])\n",
    "                flag=not flag\n",
    "            curLayer=nextLayer\n",
    "            nextLayer=[]\n",
    "        return ans                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import List\n",
    "from collections import deque\n",
    "from copy import deepcopy\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = deque()\n",
    "        stack.append(root)\n",
    "        cnt = 0\n",
    "        res = list()\n",
    "        child = deque()\n",
    "        tmp = list()\n",
    "        while stack or child:\n",
    "            if stack:\n",
    "                cur = stack.popleft()\n",
    "                tmp.append(cur.val)\n",
    "                if cur.left:\n",
    "                    child.append(cur.left)\n",
    "                if cur.right:\n",
    "                    child.append(cur.right)\n",
    "            else:\n",
    "                newtmp = deepcopy(tmp)\n",
    "                if cnt % 2 == 0:\n",
    "                    res.append(newtmp)\n",
    "                else:\n",
    "                    res.append(newtmp[::-1])\n",
    "                stack = deepcopy(child)\n",
    "                child.clear()\n",
    "                tmp.clear()\n",
    "                cnt += 1\n",
    "\n",
    "        newtmp = deepcopy(tmp)\n",
    "        if cnt % 2 == 0:\n",
    "            res.append(newtmp)\n",
    "        else:\n",
    "            res.append(newtmp[::-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        node = [root]\n",
    "        temp = [root]\n",
    "        ans = []\n",
    "        if root == None:\n",
    "            return ans\n",
    "        flag = 0\n",
    "        while(len(temp) != 0):\n",
    "            node = copy.deepcopy(temp)\n",
    "            temp = []\n",
    "            res = []\n",
    "            for i in range(len(node)):\n",
    "                res.append(node[i].val)\n",
    "                if node[i].left != None:\n",
    "                    temp.append(node[i].left)\n",
    "                if node[i].right != None:\n",
    "                    temp.append(node[i].right)\n",
    "            if flag == 1:\n",
    "                res.reverse()\n",
    "            flag = 1 - flag\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "\n",
    "        array = []\n",
    "        def preorder(node, level):\n",
    "            if not node:\n",
    "                return\n",
    "            # update val\n",
    "            if level >= len(array):\n",
    "                array.append([node.val])\n",
    "            else:\n",
    "                array[level].append(node.val)\n",
    "            \n",
    "            # left\n",
    "            preorder(node.left, level+1)\n",
    "            # right\n",
    "            preorder(node.right,level+1)\n",
    "        preorder(root,0)\n",
    "        # print(array)\n",
    "        for i,line in enumerate(array):\n",
    "            # print(i,line)\n",
    "            # print(reversed(line))\n",
    "            if i % 2:\n",
    "                array[i] = list(reversed(line))\n",
    "        # print(array)\n",
    "        return array\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        def tra(root,row):\n",
    "            if not root:\n",
    "                return []\n",
    "            if len(ans)==row:\n",
    "                ans.append([])\n",
    "            ans[row].append(root.val)\n",
    "            if root.left:\n",
    "                tra(root.left,row+1)\n",
    "            if root.right:\n",
    "                tra(root.right,row+1)\n",
    "        ans = []\n",
    "        tra(root,0)\n",
    "        for i in range(len(ans)):\n",
    "            if i%2 ==1:\n",
    "                ans[i].reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        q, res = [root], []\n",
    "        while q:\n",
    "            tmp, level = [], []\n",
    "            for node in q:\n",
    "                level.append(node.val)\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            res.append(level)\n",
    "            q = tmp\n",
    "        for i in range(len(res)):\n",
    "            res[i] = res[i] if i % 2 == 0 else res[i][::-1]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        result = []\n",
    "\n",
    "        if not root:\n",
    "            return result\n",
    "\n",
    "        temp = [root]\n",
    "\n",
    "        # true: 右, false: 左\n",
    "        flag = False\n",
    "\n",
    "        while temp:\n",
    "            n = len(temp)\n",
    "            data = []\n",
    "\n",
    "            for _ in range(n):\n",
    "                curr = temp.pop(0)\n",
    "                data.append(curr.val)\n",
    "\n",
    "                if curr.left:\n",
    "                    temp.append(curr.left)\n",
    "                if curr.right:\n",
    "                    temp.append(curr.right)\n",
    "\n",
    "            if flag:\n",
    "                data.reverse()\n",
    "                result.append(data)\n",
    "            else:\n",
    "                result.append(data)\n",
    "\n",
    "            flag = not flag            \n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ans=[]\n",
    "        cur=[root]\n",
    "        even=False\n",
    "        while cur:\n",
    "            nxt=[]\n",
    "            vals=[]\n",
    "            for node in cur:\n",
    "                vals.append(node.val)\n",
    "                if node.left: nxt.append(node.left)\n",
    "                if node.right:nxt.append(node.right)\n",
    "            cur=nxt\n",
    "            ans.append(vals[::-1] if even else vals)\n",
    "            even=not even\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        re = []\n",
    "        def treeTraverse(root: Optional[TreeNode], level:int )->None:\n",
    "            if root is None:\n",
    "                return \n",
    "            if level in dic:\n",
    "                dic[level].append(root.val)\n",
    "            else:\n",
    "                dic[level] = [root.val]\n",
    "            if root.left is not None:\n",
    "                treeTraverse(root.left, level+1)\n",
    "            if root.right is not None:\n",
    "                treeTraverse(root.right, level+1)\n",
    "        treeTraverse(root, 0)\n",
    "        for k in dic:\n",
    "            if k %2 != 0:\n",
    "                re.append(list(reversed(dic[k])))\n",
    "            else:\n",
    "                re.append(dic[k])\n",
    "        print(re)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue=collections.deque()\n",
    "        queue=[(root,0)]\n",
    "        tem_height=-1\n",
    "        ans=[]\n",
    "        while queue:\n",
    "            node,height=queue.pop(0)\n",
    "            if tem_height!=height:\n",
    "                tem_height+=1\n",
    "                ans.append([])\n",
    "            ans[-1].append(node.val)\n",
    "            print(ans)\n",
    "            if node.left:queue.append((node.left,height+1))\n",
    "            if node.right:queue.append((node.right,height+1))\n",
    "        for i in range(len(ans)):\n",
    "            if i%2==0:\n",
    "                ans[i]=ans[i]\n",
    "            else:\n",
    "                ans[i]=ans[i][-1::-1]\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        cur = [root]\n",
    "        flag = False #奇数层从左向右，偶数层从右向左\n",
    "        while cur:\n",
    "            value = []\n",
    "            nxt = []\n",
    "            for node in cur:\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "                value.append(node.val)\n",
    "            cur = nxt\n",
    "            ans.append(value[::-1] if flag else value)\n",
    "            flag = not flag\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ans = []\n",
    "        cur = [root]\n",
    "        flag = False\n",
    "        while cur:\n",
    "            vals = []\n",
    "            nxt = []\n",
    "            for node in cur:\n",
    "                vals.append(node.val)\n",
    "                if node.left:   nxt.append(node.left)\n",
    "                if node.right:  nxt.append(node.right)\n",
    "            if flag:\n",
    "                vals.reverse()\n",
    "            ans.append(vals)\n",
    "            cur = nxt\n",
    "            flag = not flag\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        depth = 0 \n",
    "        while queue:\n",
    "            # res.append([node.val for node in queue])\n",
    "            l1 = []\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    l1.append(node.left)\n",
    "                if node.right:\n",
    "                    l1.append(node.right)\n",
    "            if depth %2 == 1:\n",
    "                res.append(tmp[::-1])\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "    \n",
    "            depth += 1\n",
    "            queue = l1 \n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
